package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-17 13:45
 **/
public class LeetCode72 {

    //动态规划
    public int minDistance(String word1, String word2) {
        //word1长度
        int m = word1.length();
        //word2长度
        int n = word2.length();

        //如果有一个串是空串,那么编辑距离就为m + n次
        if (m * n == 0) {
            return m + n;
        }

        //dp[i][j]: 表示word1中的前i个字符和word2中的前j个字符的编辑距离
        int[][] dp = new int[m + 1][n + 1];

        //边界初始化
        //如果j==0表示word2为空串,那么dp[i][0] = i;
        for (int i = 0; i < m + 1; ++i) {
            dp[i][0] = i;
        }

        //如果i==0表示word1为空串,那么dp[0][j] = j;
        for (int j = 0; j < n + 1; ++j) {
            dp[0][j] = j;
        }

        for (int i = 1; i < m + 1; ++i) {
            for (int j = 1; j < n + 1; ++j) {
                int left = dp[i][j - 1];
                int down = dp[i - 1][j];
                int leftDown = dp[i - 1][j  - 1];
                //如果i,j处的字符相等,那么转移方程为dp[i][j] = 1 + min(left, down, leftDown - 1)
                //否则,转移方程为dp[i][j] = 1 + min(left, down, leftDown)
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = 1 + Math.min(left, Math.min(down, leftDown - 1));
                } else {
                    dp[i][j] = 1 + Math.min(left, Math.min(down, leftDown));
                }
            }
        }
        return dp[m][n];
    }

}
